Parti ANC diharamkan selepas pemberontakan di Sharpeville pada tahun 1960, dan Mandela sebagai tokohnya ditangkap dan dipenjarakan pada tahun 1961. Namun semangat perjuangannya tidak padam begitu saja. Mandela masih meneruskan perjuangannya dan menjalankan aktiviti bawah tanah sambil memimpin organisasi menuntut kehidupan kebangsaan yang baru, bebas daripada pengaruh aparteid.

Umkhonto we Sizwe (MK), sayap militer parti ANC dibentuk pada tahun yang sama dengan Mandela sebagai pemerintah tertingginya. Di bawah pimpinannya, dia melancarkan sabotaj terhadap pemerintahan dan ekonomi negara. Setahun kemudian, Mandela meninggalkan tanah airnya untuk mendalami latihan ketenteraan di Algeria dan mengadakan latihan untuk ahli-ahli MK yang lain.

Setelah dia kembali, dia terus ditahan dengan alasan meninggalkan negara secara haram dan mengobarkan semangat rakyat untuk bermogok. Dia didakwa bersalah dan dikenakan hukuman penjara selama lima tahun pada bulan November 1962. Sewaktu di penjara, dia didakwa dalam perbicaraan Rivonia , atas tuduhan melakukan sabotaj dan dipenjarakan seumur hidup.

Sedekad sebelum dipenjarakan, Mandela telah membidas pengenalan program Pendidikan Bantu, dan mencadangkan semua aktivis masyarakat menjadikan "setiap rumah, setiap pondok atau setiap struktur yang usang menjadi pusat ilmu".

Pulau Robben, di mana dia dipenjarakan, telah dijadikan pusat perkembangan ilmu, dan Mandela merupakan orang utama mengadakan kelas pendidikan politik. Sewaktu dipenjara, Mandela tidak pernah mengkompromikan prinsip politiknya dan menjadi sumber kekuatan banduan-banduan yang lain.

Pada tahun 70-an, dia menolak tawaran pengurangan hukumannya sekiranya dia mengiktiraf Transkei sebagai sebuah penempatan (settlement) dan bersetuju untuk tinggal di sana. Manakala pada 1980-an, dia enggan menerima tawaran Presiden Botha untuk membebaskannya dari penjara sekiranya dia menolak keganasan.